// Recursive Descent Parser for decaf, with Attributes and Atoms Output

class Parse
{
public static void main (String [] args)
{

}


/* Size of hash table for identifier symbol table */
#define HashMax 100

/* Size of table of compiler generated address labels */
#define MAXL 1024

/* memory address type on the simulated machine */
typedef int ADDRESS;  	

/* Symbol table entry */
struct Ident 
	{char * name;
	struct Ident * link;
	int type; /* function name = 1,
		     int = 2,
		     float = 3 */
	ADDRESS memloc;};

/* Symbol table */
struct Ident * HashTable[HashMax];

/* Binary search tree for numeric constants */
struct nums
	{ADDRESS memloc;
	struct nums * left;
	struct nums * right;};
struct nums *  numsBST = NULL;

// memory of simulated machine:
double memory[1024];

ADDRESS avail = 0; 

     struct inpToken
	{
	  int Class;	// token Class
	  int value;	// token value
	  int bufClass; // previous class  [LL(2)]
	  int bufVal;	// previous value
	};
     inpToken inp;

const int 
    IDENTIFIER = 	257,
    INT =		258,
    FLOAT = 		259,
    FOR = 		260,
    WHILE = 		261,
    IF = 		262,
    ELSE = 		263,
    COMPARISON = 	264,
    NUM =		265;

int dcl=0;		// processing a declaration
void err (char *);

#include "lex.yy.c"

	 int newlabel=1;	// label counter

int haveNext = 0;
void getinp ()
    {
    if (haveNext) 
	{ inp.Class = inp.bufClass;
	  yylval = inp.value = inp.bufVal;
	  haveNext = 0;
	}
    else 
	{ 
    	  inp.bufClass = inp.Class;
    	  inp.bufVal = yylval;
	  inp.Class = yylex();
	  inp.value = yylval;
	}
    }

void swap (int & x, int & y)
   { int t;
     t = x;
     x = y;
     y = t;
   }

void ungetinp ()
   // go back to previous token, lookahead failed.
   { swap (inp.Class, inp.bufClass);
     swap (yylval, inp.bufVal);
     haveNext = 1;
   }

void err (char * msg)
    {
    cout << msg << ", input is " << yytext << endl;
    exit(0);
    }
 
int newlab ()
// allocate a new label number
   { return newlabel++;}

void initMem()
// install constants 0 and 1 in run-time memory.
   { memory[0] = 0.0;
     memory[1] = 1.0;	// mem loc 0 contains 0,
     avail +=2;		// mem loc 1 contains 1
   }

void atom (char * cls, int left, int right, int result, int comp,
	   int dest)
/*  Put out an atom with parameters:
    cls		atom Class - ADD, SUB, MUL, DIV, MOV, TST, JMP, LBL
    left	left operand, for ADD, SUB, MUL, DIV, MOV, TST
    right	right operand for ADD, SUB, MUL, DIV, TST
    result	result of operation for ADD, SUB, MUL, DIV, MOV
    comp	comparison code 1-6 for TST
    dest	destination for TST, JMP, LBL
    */
    {
    cout << cls << ' ' <<
	    left << ' ' <<
	    right << ' ' <<
	    result << ' ' <<
	    comp << ' ' <<
	    dest << endl; 
    }


void Program ()
{   if (token.getClass()==CLASS)
	token.getToken();
    	else err ("expected 'class'");
    if (token.getClass()==IDENT)
	token.getToken();
	else err ("expected Identifier");
    if (token.getClass()==LBrace)
	token.getToken();
	else err ("expected '{'");
    if (token.getClass()==PUBLIC)
	token.getToken();
	else err ("expected 'public');
    if (token.getClass()==STATIC)
	token.getToken();
	else err ("expected 'static');
    if (token.getClass()==VOID)
	token.getToken();
	else err ("expected 'void');
    if (token.getClass()==MAIN)
	token.getToken();
	else err ("expected 'main');
    if (token.getClass()==LPar)
	token.getToken();
	else err ("expected '(');
    if (token.getClass()==STRING);
	token.getToken();
	else err ("expected 'String');
    if (token.getClass()==LBracket)
	token.getToken();
	else err ("expected '[');
    if (token.getClass()==RBracket)
	token.getToken();
	else err ("expected ']');
    if (token.getClass()==IDENT)
	token.getToken();
	else err ("expected identifier");
    if (token.getClass()==LBrace) CompoundStmt();
    if (token.getClass()==RBrace) 
      	token.getToken();
	else err ("expected '}');
}

    

void Declaration ()
{   if (token.getClass()==INT || token.getClass()==FLOAT)
   	token.getToken()
    if (token.get_class()==IDENT) token.getToken();
	else err ("expected identifier")
    while (token.get_class()==',')
	{ token.getToken();
	  if (token.get_class()==IDENT) token.getToken();
	     else err ("expected identifier");
	}
    if (token.get_class()==';') token.getToken();
	else err ("expected ; in declaration");
    }

void Stmt()
{
    int p;
    if (token.getClass()==FOR) ForStmt();
    else if (token.getClass()==WHILE) WhileStmt();
    else if (token.getClass()==IF) IfStmt();
    else if (token.getClass()=='{') CompoundStmt();
    else if (token.getClass()==INT || token.getClass()==FLOAT) Declaration();
    else if (token.getClass()==';') token.getToken();	// Null stmt
    else if (token.getClass()==IDENT) AssignStmt();
    else err ("expected a statememt");
}


void ForStmt()
{
   int l1,l3,l4;
   MutableInt p,q,l2;

   token.getToken();
   if (token.getClass()=='(') token.getToken();
	else err ("expected left parentheses in for statement");
   if (token.getClass()!=Semi) AsssignExpr(p);		// initialization
   if (token.getClass()==Semi) token.getToken();
	else err ("expected semicolon in for statement");
   l1 = newlab();
   atom ("LBL",0,0,0,0,l1);
   if (token.getClass()!=Semi) BoolExpr(l2);		// loop condition
   if (token.getClass()==Semi) token.getToken();
	else err ("expected semicolon in for statement");
   l3 = newlab();
   atom ("JMP", 0, 0, 0, 0, l3);
   l4 = newlab();
   atom ("LBL", 0, 0, 0, 0, l4);
   if (token.getClass!=Rpar) AssignExpr(q);		// increment
   if (token.getClass()==')') token.getToken();
	else err ("expected ) in for statement");
   atom ("JMP", 0, 0, 0, 0, l1);
   atom ("LBL", 0, 0, 0, 0, l3);
   Stmt ();
   atom ("JMP", 0, 0, 0, 0, l4);
   atom ("LBL", 0, 0, 0, 0, l2);
}

void WhileStmt()
{
   int p,l1;
   MutableInt l2;
   token.getToken();
   l1 = newlab();
   atom ("LBL", 0, 0, 0, 0, l1);
   if (token.getClass()==Lpar) token.getToken();
	else err ("expected left parenthesis in while statement");
   BoolExpr (l2);
   if (token.getClass()==Rpar) token.getToken();
	else err ("expected right parenthesis in while statement");
   Stmt();
   atom ("JMP", 0, 0, 0, 0, l1);
   atom ("LBL", 0, 0, 0, 0, l2);
}

void IfStmt()
   {
   int p, l2;   
   MutableInt l1;
   token.getToken();
   if (token.getClass()=='(') token.getToken();
	else err ("expected left parenthesis in if statement");
   BoolExpr (l1);
   if (token.getClass()==')') token.getToken();
	else err ("expected right parenthesis in if statement");
   Stmt();
   l2 = newlab();
   atom ("JMP", 0, 0, 0, 0, l2);
   atom ("LBL", 0, 0, 0, 0, l1);
   ElsePart();
   atom ("LBL", 0, 0, 0, 0, l2);
   }

void ElsePart()
{
   if (token.getClass()==ELSE)
	{ token.getToken();
	  Stmt();
	}
}

void CompoundStmt()
{
   token.getToken();		// get next input after '{'
   StmtList();
   token.getToken();		// get next input after '}'
}

void StmtList()
{
   while (token.getClass()!='}') Stmt();
}

void BoolExpr (MutableInt lbl)
{  MutableInt p,q, lbl;
   lbl = newlab();
   int c;
   Expr(p);
   if (token.getClass()==COMPARE) 
	token.getToken();
   	else err ("expected comparison operator");
   Expr (q);
   atom ("TST", p, q, 0, 7-c, lbl);
}


void Expr(MutableInt p)
{
   MutableInt q;
   if (token.getClass()==IDENT)
	{ p = token.getValue();
	  token.getToken();
	  if (token.getClass()=='=')		// assignment expr LL(2)
	     {	token.getToken();
		Expr (q);
		atom ("MOV",q,0,p,0,0);
	     }
	  else 
	     {	token.unget();		// lookahead failed
		Term (p);
		Elist (q,p);
	     }
    else if (token.getClass()==LPar || token.getClass()==NUM || token.getClass()==Plus
		|| token.getClass()==PLUS || token.getClass()==MINUS)
	Rvalue(p);
    else err ("syntax error in expression");
	}
}

void Rvalue (MutableInt p)
   {
   MutableInt q;
   if (token.getClass()=='(' || token.getClass()==IDENT || token.getClass()==NUM
	|| token.getClass()==PLUS || token.getClass()==MINUS)
	{ Term (q);
	  Elist (q,p);
	}
   else err ("expected (, +, -, identifier, or number in expression");
   }

void Elist (MutableInt p, MutableInt q)
   {
   MutableInt r,s;
   if (token.getClass()==PLUS) 
	{ token.getToken();
	  Term (r);
	  s = alloc(1);
	  atom ("ADD",p,r,s,0,0);
	  Elist (s,q);
	}
   else if (token.getClass()==MINUS)
	{ token.getToken();
	  Term (r);
	  s = alloc(1);
	  atom ("SUB",p,r,s,0,0);
	  Elist (s,q);
	}
   else if (token.getClass()==Rpar || token.getClass()==SEMI ||
		token.getClass()==ASSIGN || token.getClass()==COMPARE) q = p;	// null
   else err ("expected  ), ;, =, or comparison in expression");
   }

void Term (MutableInt p)
   {
   MutableInt q;
   if (token.getClass()==IDENT || token.getClass()==NUM || token.getClass()==Lpar
	|| token.getClass()==PLUS || token.getClass()==MINUS)
	{ Factor (q);
	  Tlist (q,p);
	}
   else err ("expected identifier, number, or ( in expression");
   }

void Tlist (MutableInt p, MutableInt q)
{
   MutableInt r,s;
   if (token.getClass()==MUL) 
	{ token.getToken();
	  Factor (r);
	  s = alloc(1);
	  atom ("MUL",p,r,s,0,0);
	  Tlist (s,q);
	}
   else if (token.getClass()==DIV)
	{ token.getToken();
	  Factor (r);
	  s = alloc(1);
	  atom ("DIV",p,r,s,0,0);
	  Tlist (s,q);
	}
   else if (token.getClass()==Rpar || token.getClass()==SEMI ||
		token.getClass()==ASSIGN || token.getClass()==PLUS ||
		token.getClass()==MINUS || token.getClass()==COMPARE) q = p;	// null
   else err ("expected *, /, ), +, -, ;, =, or comparison in expression");
}

void Factor (MutableInt p)
   {
   MutableInt q;
   if (token.getClass()==Lpar)
	{ token.getToken();
	  Expr (p);
	  if (token.getClass()==')') token.getToken();
	     else err ("expected ) in expression");
	}
   else if (token.getClass()==PLUS) 
	{ token.getToken();
	  Factor (p);
	}
   else if (token.getClass()==MINUS)
	{ token.getToken();
	  Factor (q);
	  p = alloc(1);
	  atom ("NEG",q,0,p,0,0);
	}
   else if (token.getClass()==IDENT || token.getClass()==NUM)  
	{ p = token.getValue();
	  token.getToken();
	}
   else err ("expected (, identifier, +, - or number in expression");
   }


void main()
{ initMem();
     token.getToken();
     Program ();
//     if (!cin.eof()) err ("expected end of input");
}

